'''
Created on Mar 20, 2015

@author: root
'''

from random import randint
import time
import math
import ctypes 
import os

LIB_PATH = r'./algo_c'
challendge_lib_path = os.path.join(LIB_PATH, 'libchalledge.so')

def generate_list2(n, max):
    return [randint(0, max) for i in range(n)]

'''
Question1:

A list which contains only 0 and 1, find a sub-list(start, end), and change 1 to 0 and 0 to 1 with the sub-list, to make sure that, 
there are most number of 1 in the total list


Answers:

The following 3 function with more and more faster to do this question
'''

def quick_choose(l):
    l1 = map(lambda x: 1 if x == 1 else -1, l)
    s = [(i,j,reduce(lambda x,y: x+y, l1[i:j+1], 0)) for i in range(len(l1)) for j in range(len(l1))]
    b = s[0]
    for item in s:
        if b[2] > item[2]:
            b = item
    print b

def quick_choose_e(l):
    l1 = map(lambda x: 1 if x == 1 else -1, l)
    l2 = [index for (index, value) in enumerate(l1) if value == -1]
    s = [(i,j,reduce(lambda x,y: x+y, l1[i:j+1], 0)) for i in l2 for j in l2]
    for item in s:
        if s[0][2] > item[2]:
            s[0] = item
    print s[0] 

def quick_choose_e2(l):
    l1 = map(lambda x: 1 if x == 1 else -1, l)
    l2 = [index for (index, value) in enumerate(l1) if value == -1]
    s = []
    i = 0 
    while i<len(l2):
        start_flag = False 
        start = i
        while i<len(l2) and l2[i]==l2[i-1]+1:
            start_flag = True
            i += 1
        j = i
        while j<len(l2):
            end_flag = False
            while j<len(l2) and l2[j]==l2[j-1]+1:
                end_flag = True
                j += 1
            end = j-1 if end_flag else j
            s.append((l2[start], l2[end], reduce(lambda x,y: x+y, l1[l2[start]:l2[end]+1])))
            if not end_flag:
                j += 1

        if not start_flag:
            i += 1
    for item in s:
        if s[0][2] > item[2]:
            s[0] = item
    print s[0] 

def test_question_1():
    l = generate_list2(1000, 1)
    print l
    t0 = time.time()
    quick_choose(l)
    t1 = time.time()
    quick_choose_e(l)
    t2 = time.time()
    quick_choose_e2(l)
    t3 = time.time()
    print t1 - t0
    print t2 - t1
    print t3 - t2

def get_prime_number(n):    
    l = [1] * (n+1)
    for i in range(2, int(math.sqrt(n))+1):
        if l[i] == 0:
            continue
        j = 2 
        while j*i<=n+1:
            l[j*i] = 0
            j += 1 
    print [index for index, value in enumerate(l) if value == 1][1:]

def get_number_with_certain_sum(l, sum):
    i = 0 
    j = len(l)-1
    result = []
    while True:
        tmp_sum = l[i]+l[j]
        if tmp_sum>sum:
            j -= 1
        elif tmp_sum==sum: 
            result.append((i, j))
            i += 1
            j -= 1
        else:
            i += 1
        if i==j:
            break
    return result

def is_prime(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num%i == 0:
            return False
    return True

def get_largetst_prime_factor_of_a_number(num):
    factors = [(i, num/i) for i in range(1, int(math.sqrt(num))+1) if num%i==0]
    for factor in factors:
        if is_prime(factor[1]):
            largest_factor = factor[1]
        elif is_prime(factor[0]):
            largest_factor = factor[0]
    return largest_factor

def get_largetst_prime_factor_of_a_number_e(num):
    for i in range(2, int(math.sqrt(num))+1):
        if num==i:
            return num
        while num%i == 0 and num != i:
            num /= i
    return num

def get_large_number(n):
    l = [0]
    for i in range(n):
        l[-1] += 1
        for j in range(len(l)):
            if l[-1-j]==10:
                l[-1-j] = 0
                if -(-1-j)==len(l): # need new bit
                    l.insert(-2-j, 1)
                else: # no need new bit. add 1
                    l[-2-j] += 1
    print ''.join([str(item) for item in l])

def get_large_number_c(n):
    challendge = ctypes.CDLL(challendge_lib_path)
    challendge.get_large_number(n)

def main():
    #test_question_1()
    #get_prime_number(100)
    #print get_number_with_certain_sum(range(15), 14)
    """
    n = 7383519593589835 
    t0 = time.time()
    print get_largetst_prime_factor_of_a_number(n)
    t1 = time.time()
    print get_largetst_prime_factor_of_a_number_e(n)
    t2 = time.time()
    
    print t1 - t0
    print t2 - t1
    """
    get_large_number_c(1000)

if __name__ == '__main__':
    main()